package offerbook;

/**
 * 优点是比较次数少，查找速度快，平均性能好；
 * <p>
 * 其缺点是要求待查表为有序表，且插入删除困难。
 * <p>
 * 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
 * 二分查找的应用见
 *
 */
public class Code08_HalfSearch {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 4, 5, 7, 11};
        System.out.println(binarySearch1(arr, 6));
        System.out.println(binarySearch2(arr, 6, 0, arr.length - 1));
    }

    public static boolean binarySearch1(int[] arr, int target) {
        if (arr == null || target < arr[0] || target > arr[arr.length - 1]) {
            return false;
        }
        int left = 0;
        int right = arr.length - 1;
        int mid = (left + right) / 2;
        while (left <= right) {
            if (target < arr[mid]) {
                right = mid - 1;
            } else if (target > arr[mid]) {
                left = mid + 1;
            } else {
                return true;
            }
            mid = (left + right) / 2;
        }
        return false;
    }

    public static boolean binarySearch2(int[] arr, int target, int left, int right) {
        if (arr == null || target < arr[0] || target > arr[arr.length - 1]) {
            return false;
        }
        int mid = (left + right) >> 1;
        while (left <= right) {
            if (target < arr[mid]) {
                return binarySearch2(arr, target, left, mid - 1);
            } else if (target > arr[mid]) {
                return binarySearch2(arr, target, mid + 1, right);
            } else {
                return true;
            }
        }
        return false;

    }
}
